package 剑指Offer._6170;

import general_class.TreeNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/12/23 13:11
 * 二叉搜索树的最近公共祖先
 * 算法：深度优先搜索
 * 1、如果 p、q 在树的两侧，则返回 root
 * 2、如果 p 或者 q 为 root，则返回 root
 * 3、p q 第一次分开的地方，就是最近公共祖先
 */
public class _68I {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (p.val > root.val && q.val > root.val) root = root.left;
            else if (p.val < root.val && q.val < root.val) root = root.right;
            else break;
        }
        return root;
    }

}
